결정론적 튜링 기계

튜링 기계는 무한히 긴 테이프, 테이프를 읽고 쓰는 헤드, 그리고 유한한 상태를 기록하는 제어 장치로 구성된다. 테이프는 셀이라는 단위로 나뉘며, 각 셀에는 기호가 하나씩 기록된다. 헤드는 한 번에 하나의 셀만 읽거나 쓸 수 있으며, 제어 장치는 현재 상태와 헤드가 읽은 기호에 따라 다음 동작을 결정한다.

제어 장치의 핵심은 전이 함수이다. 이 함수는 현재 상태와 현재 읽은 기호를 입력으로 받아, 다음 상태, 테이프에 쓸 기호, 그리고 헤드의 이동 방향(왼쪽, 오른쪽, 정지)을 출력한다. 결정론적 튜링 기계에서는 이 전이 함수가 함수의 수학적 정의를 완전히 만족한다. 즉, 같은 입력(현재 상태, 현재 기호)에 대해서는 항상 동일한 출력(다음 상태, 쓸 기호, 이동 방향)이 유일하게 결정된다.

이러한 구성 요소들은 튜링 기계가 알고리즘을 수행하는 방식을 추상화한 것이다. 테이프는 무제한의 메모리를, 제어 장치는 프로세서와 프로그램을, 전이 함수는 실행할 명령어 집합을 상징한다. 따라서 결정론적 튜링 기계는 현대 컴퓨터의 이론적 모델로서 그 기본 구조를 제공한다.

결정론적 튜링 기계에서 '결정론적 동작'이란, 기계의 모든 단계에서 다음 행동이 현재 상황에 의해 완전히 예정되어 있다는 것을 의미한다. 구체적으로, 기계는 현재 상태와 테이프 헤드가 읽고 있는 기호라는 두 가지 정보만을 바탕으로, 유일하게 정해진 다음 상태, 테이프에 쓸 기호, 그리고 헤드의 이동 방향(좌측, 우측, 정지)을 결정한다. 이는 전이 함수가 하나의 입력에 대해 하나의 출력만을 지정하는 함수라는 점에서 비롯된다.

이러한 결정론적 특성은 계산 과정에 예측 가능성을 부여한다. 동일한 입력과 동일한 초기 상태로 결정론적 튜링 기계를 작동시키면, 그 계산 경로는 항상 동일하게 재현된다. 이는 현대의 범용 디지털 컴퓨터가 기본적으로 결정론적으로 동작하는 것과 맥을 같이한다. 컴퓨터의 CPU가 특정 기계어 명령어를 실행할 때 그 결과가 항상 동일한 것과 유사한 원리이다.

결정론적 동작의 반대 개념은 비결정론적 튜링 기계의 동작이다. 비결정론적 모델은 하나의 상황에서 여러 가지 가능한 다음 행동을 가질 수 있으며, 이는 이론적 탐색 공간을 동시에 고려하는 추상적 개념으로, 계산 복잡도 이론에서 NP 문제 등을 분석하는 데 유용하게 쓰인다. 그러나 실제 물리적 기계로 구현 가능한 계산 모델의 기준은 결정론적 튜링 기계가 된다.

전이 함수는 결정론적 튜링 기계의 핵심 구성 요소로, 기계의 논리를 정의한다. 이 함수는 현재 상태와 헤드가 읽은 테이프 기호를 입력으로 받아, 다음 상태, 테이프에 쓸 기호, 그리고 헤드의 이동 방향(좌측, 우측, 정지)이라는 세 가지 출력을 유일하게 결정한다. 이렇게 하나의 입력에 대해 하나의 결과만 존재하는 것이 결정론적 동작의 본질이다.

계산 과정은 초기 상태에서 시작하여 전이 함수를 반복적으로 적용하는 방식으로 진행된다. 기계는 테이프의 특정 셀을 읽고, 그 기호와 현재 상태에 따라 전이 함수를 참조하여 새로운 기호를 쓰고, 상태를 변경하며, 헤드를 이동시킨다. 이 과정은 전이 함수가 '정지' 상태로의 이동을 명령할 때까지 계속된다. 정지 상태에 도달하면, 테이프에 기록된 내용이 계산의 최종 출력으로 간주된다.

이러한 계산 과정은 모든 현대 디지털 컴퓨터의 동작 원리를 추상화한 모델이다. 알고리즘의 실행은 결국 초기 입력(테이프 내용)과 프로그램(전이 함수의 집합)에 따라 이러한 상태 전이의 연속으로 이해될 수 있다. 따라서 결정론적 튜링 기계는 어떤 문제가 계산 가능성을 가지는지, 즉 알고리즘으로 해결될 수 있는지를 논의하는 이론적 토대를 제공한다.

전이 함수는 보통 상태 다이어그램이나 상태 테이블로 표현된다. 상태 테이블은 행을 현재 상태로, 열을 읽은 기호로 구성하며, 각 셀에는 (쓸 기호, 이동 방향, 다음 상태)의 순서쌍이 기록된다. 이 표를 따라 기계의 모든 동작을 추적할 수 있어, 계산 과정을 명확하고 체계적으로 분석하는 데 유용하다.

튜링 기계의 계산 과정은 특정 조건이 충족될 때 종료되며, 이를 정지 조건이라고 한다. 결정론적 튜링 기계는 유한한 단계 내에 이러한 정지 조건에 도달하거나, 혹은 영원히 정지하지 않는 두 가지 가능성을 가진다.

정지 조건은 일반적으로 튜링 기계의 전이 함수에 의해 정의된다. 전이 함수는 현재 상태와 테이프 헤드가 읽은 기호를 입력으로 받아, 다음 상태, 테이프에 쓸 기호, 헤드의 이동 방향을 출력한다. 만약 현재 상태와 읽은 기호의 조합에 대해 전이 함수가 정의되어 있지 않다면, 튜링 기계는 더 이상 진행할 수 없어 계산을 멈추게 된다. 이렇게 정의되지 않은 조합에 도달하는 것을 정지 상태에 도달했다고 본다. 또한, 일부 정의에서는 특별한 '정지 상태'를 명시적으로 두고, 이 상태로 전이되는 것을 계산의 종료로 규정하기도 한다.

튜링 기계가 정지 조건에 도달하면, 그 시점의 테이프 위에 기록된 기호의 배열이 계산의 출력 결과가 된다. 반면, 정지 조건에 절대 도달하지 않고 무한히 동작하는 경우도 있다. 예를 들어, 헤드가 한 방향으로만 계속 이동하거나, 상태와 테이프 기호의 조합이 순환을 이루는 경우에 무한 루프에 빠질 수 있다. 한 계산이 주어진 입력에 대해 최종적으로 정지하는지 여부를 판단하는 문제는 정지 문제로 알려져 있으며, 이는 계산 불가능한 대표적인 문제이다.

계산 이론에서 결정론적 튜링 기계는 가장 기본적이고 핵심적인 계산 모델이다. 이 모델은 앨런 튜링이 1936년에 제안한 이후, 계산 가능성과 알고리즘의 개념을 정의하는 표준 도구로 자리 잡았다. 모든 계산 가능한 함수는 결정론적 튜링 기계로 계산할 수 있다는 처치-튜링 테제는 현대 컴퓨터 과학의 이론적 기초를 제공한다.

이 모델은 계산 복잡도 이론의 표준 모델로서도 사용된다. 예를 들어, 시간 복잡도 클래스인 P와 NP는 결정론적 튜링 기계와 비결정론적 튜링 기계를 기준으로 정의된다. 결정론적 튜링 기계는 형식 언어 이론에서도 중요한 역할을 하며, 재귀 열거 언어와 같은 언어 계층을 정의하는 데 사용된다.

다른 계산 모델과의 관계에서도 결정론적 튜링 기계는 기준점이 된다. 람다 대수, 재귀 함수, 포스트 머신 등 다른 여러 계산 모델은 결정론적 튜링 기계와 계산 능력이 동등함이 증명되어 있다. 이는 튜링 기계의 계산 능력이 매우 강력하며, 현대 디지털 컴퓨터의 이론적 한계를 대표한다는 것을 의미한다.

결정론적 튜링 기계는 계산 이론에서 가장 기본적인 모델로, 다른 여러 계산 모델과 밀접한 관계를 가진다. 이 모델은 앨런 튜링이 제안한 이후, 다양한 계산 능력을 가진 모델들을 비교하고 분류하는 기준점 역할을 해왔다.

가장 직접적인 비교 대상은 비결정론적 튜링 기계이다. 결정론적 튜링 기계는 각 단계에서 다음 동작이 유일하게 결정되지만, 비결정론적 튜링 기계는 여러 가능한 동작 중 하나를 '추측'하여 선택할 수 있다. 흥미롭게도, 두 모델은 동일한 범주의 계산 가능성을 가진다. 즉, 결정론적 튜링 기계로 풀 수 있는 문제는 비결정론적 튜링 기계로도 풀 수 있으며, 그 역도 성립한다. 그러나 계산 복잡도 이론에서는 이 둘의 차이가 중요해진다. 예를 들어, P-NP 문제는 결정론적 튜링 기계로 다항 시간에 풀 수 있는 문제들의 집합(P)과 비결정론적 튜링 기계로 다항 시간에 풀 수 있는 문제들의 집합(NP)이 같은지 묻는 유명한 미해결 문제이다.

다른 계산 모델들과의 관계는 다음과 같이 정리할 수 있다.

이러한 비교를 통해 결정론적 튜링 기계는 계산 가능성을 논의하는 데 있어 보편적이고 강력한 기준 모델임이 확인된다. 모든 현실적인 컴퓨터와 대부분의 형식 언어 계층 구조는 이 모델의 계산 능력 안에 포함되며, 이는 처치-튜링 논제의 핵심 근거가 된다.